package org.aplombh.java.awcing.basic.dp.linearDP;

import java.io.*;

/**
 * 给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
 * <p>
 * 7
 * 3   8
 * 8   1   0
 * 2   7   4   4
 * 4   5   2   6   5
 * 输入格式
 * 第一行包含整数 n，表示数字三角形的层数。
 * <p>
 * 接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。
 * <p>
 * 输出格式
 * 输出一个整数，表示最大的路径数字和。
 * <p>
 * 数据范围
 * 1≤n≤500,
 * −10000≤三角形中的整数≤10000
 * 输入样例：
 * 5
 * 7
 * 3 8
 * 8 1 0
 * 2 7 4 4
 * 4 5 2 6 5
 * 输出样例：
 * 30
 */
public class DigitalTriangle_898 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(reader.readLine());
        DigitalTriangle digitalTriangle = new DigitalTriangle(n);
        for (int i = 1; i <= n; i++) {
            String[] str = reader.readLine().split(" ");
            for (int j = 1; j <= i; j++) {
                digitalTriangle.s[i][j] = Integer.parseInt(str[j - 1]);
                digitalTriangle.f[i][j] = Integer.parseInt(str[j - 1]);
            }
        }
        System.out.println(digitalTriangle.solve());
    }
}

class DigitalTriangle {
    public static final int N = 510;
    int n;
    int[][] f = new int[N][N];
    int[][] s = new int[N][N];
    int[][] path = new int[N][N];

    public DigitalTriangle(int n) {
        this.n = n;
    }

    public int solve() {
        // 从下往上寻找路径
        // 从上往下找需要判断边界条件
        for (int i = n - 1; i > 0; i--) {
            for (int j = 1; j <= i; j++) {
                if (f[i + 1][j] < f[i + 1][j + 1]) {
                    f[i][j] += f[i + 1][j + 1];
                    path[i][j] = 2;
                } else {
                    f[i][j] += f[i + 1][j];
                    path[i][j] = 1;
                }
            }
        }
        path();
        return f[1][1];
    }

    public void path() {

        int capacity = f[1][1];
        System.out.println(1 + " " + 1 + " " + s[1][1]);
        for (int i = 1, j = 1; i < n && capacity > 0; i++) {
            capacity -= s[i][j];
            if (path[i][j] == 1) {
                System.out.println((i + 1) + " " + j + " " + s[i + 1][j]);
            } else if (path[i][j] == 2) {
                System.out.println((i + 1) + " " + (j + 1) + " " + s[i + 1][j + 1]);
                j++;
            }
        }
    }
}
